package 剑指offer;

public class 剑指Offer04二维数组中的查找 {
    public static void main(String[] args) {
        int[][] arr = new int[][]{
                {1,4,7,11,15},
                {2,5,8,12,19},
                {3,6,9,16,22},
                {10,13,14,17,24},
                {18,21,23,26,30}
        };
        System.out.println(findNumberIn2DArray(arr, 20));
    }
    //方法1：线性搜索
    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        //数组的规律：左->右 升序   上->下 升序，给定任意一数字，判断是否存在
        /*
        思路：
        1.从左下角，或者右上角开始，例如：左下角比他大的向右搜索，比他小的小伤搜索
        2.搜索到了发回true，搜索不到，终止条件，rol（行）< 0 || col（列）> n(总列数)
         */
        if(matrix.length <= 0) {
            return false;
        }
        int rol = matrix.length;//二位数组的行数
        int col = matrix[0].length;//二位数组的列数
        //从左下角开始，例如开始搜索8;
        int colNo = 0;
        int rolNo = rol-1;
        while (rolNo >= 0 && colNo < col){
            if (matrix[rolNo][colNo] > target){//如果比target大，向上搜索
                rolNo--;
            }else if (matrix[rolNo][colNo] < target){//如果比他小，向有遍历
                colNo++;
            }else if (matrix[rolNo][colNo] == target){
                return true;
            }else {
                return false;
            }
        }
        //如果循环结束，没有返回，说明不存在，返回false;
        return false;
    }
}
